class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        size = len(s)

        # dp[i][j] = 令字符串[i,j]变为回文串需要删除的字符数
        dp = [[float("inf")] * size for _ in range(size)]

        for i in range(size):
            dp[i][i] = 0

        for length in range(2, size + 1):
            for i in range(size - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    if length == 2:
                        dp[i][j] = 0
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                else:
                    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1

        return dp[0][-1] <= k


if __name__ == "__main__":
    print(Solution().isValidPalindrome(s="abcdeca", k=2))  # True
